731C - Socks - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define all(x) x.begin(), x.end()
const int mod = 1e9+7;
const int maxn = 2e5+5;

vector<int> graph[maxn];
int col[maxn], visited[maxn];

int cnt;
map<int, int> freq;

void dfs(int u){
    visited[u] = 1;
    freq[col[u]] = freq[col[u]]+1;
    cnt++;
    for(int x : graph[u]){
        if(visited[x] == 0){
            dfs(x);
        }
    }
}


int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    int n, m, k;
    cin >> n >> m >> k;
    for(int i = 0; i < n; i++) cin >> col[i];
    for(int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        a--; b--;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    int sol = 0;
    for(int i = 0; i < n; i++){
        if(visited[i] == 0){
            freq.clear();
            cnt = 0;
            dfs(i);
            sol += cnt - max_element(freq.begin(), freq.end(), [](auto x, auto y){ return x.second < y.second; })->second;;
        }
    }

    cout << sol;

    return 0;
}